package problem213;

//213. 打家劫舍2
//https://leetcode.cn/problems/house-robber-ii/

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0] + rob1(nums, 2, n-1), rob1(nums, 1, n));
    }
    public int rob1(int[] nums, int begin, int end) {
        if(begin >= end) return 0;
        int[] f = new int[end];
        int[] g = new int[end];
        g[begin] = nums[begin];
        for(int i = begin+1; i<end; i++) {
            g[i] = f[i-1] + nums[i];
            f[i] = Math.max(g[i-1], f[i-1]);
        }
        return Math.max(f[end-1], g[end-1]);
    }
}

/*
分两种情况:
1.第0个位置的元素拿
  转化为 nums[0] + rob1(nums, n+2, n-1);
2.第0个位置的元素不拿 
  转化为 rob1(nums, n+1, n);

rob1 为打家劫舍1 的代码思路:

g[i]: 到第i个房子并且拿第i个房间现金的最大金额
g[i] = f[i-1] + nums[i];
f[i]: 到第i个房子并且不拿第i个房间现金的最大金额
f[i] = Math.max(g[i-1], f[i-1]);

*/